package leetcode110

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 左右子树高度差小于1, 左右子树也满足
func isBalanced(root *TreeNode) bool {

	if root == nil {
		return true
	}
	return abs(height(root.Left)-height(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

// 空为0,否则为左右子树最大+1
func height(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(height(root.Left), height(root.Right)) + 1
}

func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}
